package com.fw.leetcode;

import java.util.ArrayDeque;

public interface LeetCode {
    interface LinkedList {
        // Definition for singly-linked list.
        class ListNode {
            public int val;
            public ListNode next;
            public ListNode() {}
            public ListNode(int val) { this.val = val; }
            public ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        }

        default ListNode build(int[] nodes) {
            ListNode head = null;
            ListNode prev = null;
            for (int node : nodes) {
                ListNode cur = new ListNode(node);
                if (prev == null) {
                    head = cur;
                } else {
                    prev.next = cur;
                }
                prev = cur;
            }
            return head;
        }

        default ListNode concat(ListNode l1, ListNode l2) {
            ListNode prev = l1;
            while (prev.next != null) {
                prev = prev.next;
            }
            prev.next = l2;
            return l1;
        }

        default boolean assertEquals(ListNode l1, ListNode l2) {
            while ((l1 != null && l2 != null && l1.val == l2.val)) {
                l1 = l1.next;
                l2 = l2.next;
            }
            return l1 == null && l2 == null;
        }
    }

    interface Tree {
        //Definition for a binary tree node.
        class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode() {}
            public TreeNode(int val) { this.val = val; }
            public TreeNode(int val, TreeNode left, TreeNode right) {
                this.val = val;
                this.left = left;
                this.right = right;
            }

            private static TreeNode buildBinaryTreeRecursion(Integer[] rootArr, int i) {
                /*
                 * [0,1,2,3,4,5,6]
                 * layer
                 *  0                0
                 *  1         1            2
                 *  2      3     4      5     6
                 *
                 * [1,null,2,3]  <- [非满二叉树 不满足]
                 *       1
                 *   -       2
                 *         3
                 * Features: （满二叉树规则，非满二叉树不满足）
                 *  1) parent[i] -> child[2*i+1] & child[2*i+2]
                 *  2) maxNodes[layer] = 2^layer
                 *  3) maxLayerNodes = 2^(log n)
                 */
                if (i >= rootArr.length || rootArr[i] == null) {
                    return null;
                }
                return new TreeNode(rootArr[i],
                        buildBinaryTreeRecursion(rootArr, 2 * i + 1),
                        buildBinaryTreeRecursion(rootArr, 2 * i + 2));
            }

            private static TreeNode buildBinaryTreeInLevel(Integer[] rootArr) {
                /*
                 * 解决非满二叉树情形下的构建
                 * 层次遍历
                 *
                 * [1,null,2,3]  <- [非满二叉树]
                 *       1
                 *   -       2
                 *         3
                 */
                if (rootArr.length == 0) return null;
                TreeNode root = new TreeNode(rootArr[0]);
                ArrayDeque<TreeNode> stack = new ArrayDeque<>();
                stack.push(root);
                int i = 1;
                int layerSize = 1; // 每层节点数
                int layerEmptySize = 0; // 每层空节点数
                while (i < rootArr.length) {
                    while (layerSize-- >= 0) {
                        TreeNode node = stack.pop();
                        // 尝试构建 node 的左节点
                        if (i >= rootArr.length) {
                            return root;
                        }
                        if (rootArr[i] != null) {
                            node.left = new TreeNode(rootArr[i]);
                            stack.push(node.left);
                        } else {
                            layerEmptySize += 2; // 记录空节点的两个子节点也为空
                        }
                        i++;
                        // 尝试构建 node 的右节点
                        if (i >= rootArr.length) {
                            return root;
                        }
                        if (rootArr[i] != null) {
                            node.right = new TreeNode(rootArr[i]);
                            stack.push(node.right);
                        } else {
                            layerEmptySize += 2;
                        }
                        i++;
                    }
                    layerSize = (layerSize << 1) - layerEmptySize; // 计算下层的实际节点数，去除空节点
                }
                return root;
            }
        }

        default TreeNode buildBinaryTree(Integer[] rootArr) {
            return TreeNode.buildBinaryTreeInLevel(rootArr);
        }
    }
}
